/*
 * @Author: liusheng
 * @Date: 2022-04-12 15:48:36
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-12 16:39:44
 * @Description: 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 
剑指 Offer II 025. 链表中的两数相加
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

 
示例1：


输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/

 */

#include <stack>
using namespace std;

struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
};

//resverse ListNode solution
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode * pre = nullptr;
        ListNode * cur = nullptr;

        //reverse l1
        if (l1 && l1->next)
        {
            cur = l1;
            //reverse l1
            while (cur)
            {
                ListNode * next = cur->next;
                cur->next = pre;

                pre = cur;
                cur = next;
            }
            l1 = pre;
        }

        //reverse l2
        if (l2 && l2->next)
        {
            pre = nullptr;
            cur = l2;
            while (cur)
            {
                ListNode * next = cur->next;
                cur->next = pre;

                pre = cur;
                cur = next;
            }
            l2 = pre;
        }
        

        ListNode * p1 = l1;
        ListNode * p2 = l2;

        char carry = 0;
        ListNode * head = nullptr;
        //caculate sum
        //reverse insert
        while (p1 || p2 || carry)
        {
            int sum = 0;
            if (p1)
            {
                sum += p1->val;
                p1 = p1->next;
            }

            if (p2)
            {
                sum += p2->val;
                p2 = p2->next;
            }

            sum += carry;
            
            carry = sum / 10;
            sum %= 10;
            //reverse insert
            ListNode * node = new ListNode(sum);
            node->next = head;
            head = node;
        }

        return head;
    }
};

//two stack solution
class Solution2 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> st1;
        stack<int> st2;

        ListNode * p1 = l1;
        ListNode * p2 = l2;

        while (p1)
        {
            st1.push(p1->val);
            p1 = p1->next;
        }

        while (p2)
        {
            st2.push(p2->val);
            p2 = p2->next;
        }

        char carry = 0;
        int sum = 0;
        ListNode * head = nullptr;
        while (!st1.empty() || !st2.empty() || carry != 0)
        {
            sum = 0;
            if (!st1.empty())
            {
                sum += st1.top();
                st1.pop();
            }

            if (!st2.empty())
            {
                sum += st2.top();
                st2.pop();
            }

            sum += carry;
            carry = sum / 10;
            sum %= 10;
            // printf("sum=%d,carry=%d\n",sum,carry);

            //reverse insert node
            ListNode * node = new ListNode(sum);
            node->next = head;
            head = node;
        }

        return head;
    }
};
